package leetcode.top100;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ：zsy
 * @date ：Created 2022/10/23 9:37 PM
 * @description：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
 */
public class _017_电话号码的字母组合 {
    @Test
    public void test() {
        System.out.println(new Solution().letterCombinations("23"));
    }

    class Solution {

        public List<String> letterCombinations(String digits) {
            List<String> ans = new ArrayList<>();
            if (digits.length() == 0) return ans;
            Map<Character, String[]> map = new HashMap<>();
            initMap(map);
            dfs(ans, digits, map, new StringBuilder(), 0);
            return ans;
        }

        private void dfs(List<String> ans, String digits, Map<Character, String[]> map, StringBuilder builder, int idx) {
            if (idx == digits.length()) {
                ans.add(builder.toString());
                return;
            }
            char ch = digits.charAt(idx);
            String[] strs = map.get(ch);
            for (String str : strs) {
                StringBuilder curBuilder = new StringBuilder(builder);
                curBuilder.append(str);
                dfs(ans, digits, map, curBuilder, idx + 1);
            }
        }

        public void initMap(Map<Character, String[]> map) {
            map.put('2', new String[]{"a", "b", "c"});
            map.put('3', new String[]{"d", "e", "f"});
            map.put('4', new String[]{"g", "h", "i"});
            map.put('5', new String[]{"j", "k", "l"});
            map.put('6', new String[]{"m", "n", "o"});
            map.put('7', new String[]{"p", "q", "r", "s"});
            map.put('8', new String[]{"t", "u", "v"});
            map.put('9', new String[]{"w", "x", "y", "z"});
        }
    }
}
